package day_2022_9_to_12.Day;

import java.util.LinkedList;

/**
 * @author haomin
 * @date 2022/11/16 21:01
 **/
public class Day72_1_Num775_IsIdealPermutation {

    // 超时
    class Solution {
        public boolean isIdealPermutation(int[] nums) {
            int res = 0;
            for(int i = 0; i < nums.length - 1; ++i) {
                for(int j = i + 1; j < nums.length; ++j) {
                    if(nums[i] > nums[j]) res++;
                }
                if(nums[i] > nums[i+1]) res--;
            }
            return res == 0;
        }
    }

    class Solution2 {
        public boolean isIdealPermutation(int[] nums) {
            int max = nums[0];
            for(int i = 2; i < nums.length; ++i) {
                if(nums[i] < max) return false;
                max = Math.max(max, nums[i-1]);
            }
            return true;
        }
    }
}